import java.util.Stack;

public class ValidParentheses {
	public boolean isValid(String s) {
		Stack<Character> stack = new Stack<Character>();
		char tmp = '0';
		for (int i = 0; i < s.length(); i++) 
		{
			tmp = s.charAt(i);
			if (!isClose(tmp)) 
			{
				stack.push(tmp);
			} 
			else 
			{
				if (!stack.isEmpty()) 
				{
					if (isMatch(stack.peek(), tmp)) 
					{
						stack.pop();
					}
					else 
					{
						return false;
					}
				}
				else 
				{
					return false;
				}
			}
		}
		if(!stack.isEmpty())
			return false;
		return true;
	}

	public boolean isClose(char s) {
		if (s == '(' || s == '[' || s == '{')
			return false;
		else
			return true;
	}

	public boolean isMatch(char f, char s) {

		switch (f) {
		case '(':
			if (s == ')')
				return true;
			break;
		case '{':
			if (s == '}')
				return true;
			break;
		case '[':
			if (s == ']')
				return true;
			break;
		default:
			break;
		}
		return false;
	}
}
